#include <iostream>
#include <fstream>
#include <string>
#include "BiGraph.h"

using namespace std;

void printGraph(BiGraph<int>* graph) {
    for(BiGraph<int>::Vertex_Iterator i = graph->begin(); i!= graph->end(); ++i){
        for( BiGraph<int>::Out_Edge_Iterator y=i->out_edge_begin(); y!= i->out_edge_end(); ++y){
            cout<<(y->get_name()).first<<" - "<<(y->get_name()).second<<endl;
        }
    }
    cout<<endl;
}

void readGraph(BiGraph<int>& graph) {
    fstream input("in.txt", fstream::in);
    if (!input.is_open()) {
        cout<<"Can not open file!\n";
        exit(1);
    }
    int count, a, b;
    double w;
    input>>count;

    for (int i = 0; i < count; ++i) {
        input>>a>>b>>w;
        graph.add_edge(a, b, w);
    }
}

void addEdge(BiGraph<int>& graph, BiGraph<int>* mst) {
    int a, b;
    double w;
    cin>>a>>b>>w;

    if (graph.get_vertex(a) == NULL) {
        cout<<"Error: no vertex \'"<<a<<"\'\n\n";
        return;
    }

    if (graph.get_vertex(b) == NULL) {
        cout<<"Error: no vertex \'"<<a<<"\'\n\n";
        return;
    }

    if (graph.get_edge(a, b) != NULL) {
        cout<<"Error: edge already exists\n\n";
        return;
    }

    graph.add_edge(a, b, w);
    mst->DFS(b); // строим путь обхода MST

    double max = w;
    BiGraph<int>::Vertex* from = graph.get_vertex(b);
    BiGraph<int>::Vertex* to = graph.get_vertex(a);

    for (BiGraph<int>::Vertex* i = to; i->parent != NULL; i = i->parent) {
    // ищем ребро с весом, большим, чем у добавляемого, в порядке обхода DFS от вершины a до b
        double weight = graph.get_edge(i, i->parent)->get_weight();
        if (weight > max) {
            max = weight;
            from = i;
            to = i->parent;
        }
    }

    if (from != graph.get_vertex(b) || to != graph.get_vertex(a)) {
        mst->add_edge(a, b, w);
        mst->delete_edge(from, to);
        // MST не нарушится, т.к. мы, удалив ребро, разделили его на 2 части - в одной вершина a,
        // в другой - b, и мы добавляем ребро (a, b)
    }

    printGraph(mst);
}

void canReach(BiGraph<int>::Vertex* v, BiGraph<int>* graph) {
    v->closed = true;

    for (BiGraph<int>::Out_Edge_Iterator i = v->out_edge_begin(); i != v->out_edge_end(); ++i) {
        BiGraph<int>::Vertex* u = i->get_vertices().second;
        if (!u->closed) { canReach(u, graph); }
    }
}

bool deleteEdge(BiGraph<int>& graph, BiGraph<int>* mst) {
    int a, b;
    cin>>a>>b;

    if (graph.get_vertex(a) == NULL) {
        cout<<"Error: no vertex \'"<<a<<"\'\n\n";
        return true;
    }

    if (graph.get_vertex(b) == NULL) {
        cout<<"Error: no vertex \'"<<a<<"\'\n\n";
        return true;
    }

    if (graph.get_edge(a, b) == NULL) {
        cout<<"Error: edge do not exist\n\n";
        return true;
    }

    graph.delete_edge(a, b);

    if (mst->get_edge(a, b) != NULL) { // если ребро не входило в MST - ничего не делаем
        mst->delete_edge(a, b);
        mst->init();

        canReach(&(*mst->begin()), mst); // проверяем достижимость остальных вершин из данной

        double min = numeric_limits<double>::max();
        BiGraph<int>::Vertex* from = NULL;
        BiGraph<int>::Vertex* to = NULL;

        for (BiGraph<int>::Vertex_Iterator i = graph.begin(); i != graph.end(); ++i) {
            for (BiGraph<int>::Vertex_Iterator j = graph.begin(); j != graph.end(); ++j) {
                BiGraph<int>::Edge* edge = graph.get_edge(i->get_name(), j->get_name());
                if (mst->get_vertex(i->get_name())->closed && !mst->get_vertex(j->get_name())->closed && edge != NULL) {
                // есть ребро, соединяющее соединяющих две доли старого MST
                    if (edge->get_weight() < min) {
                        min = edge->get_weight();
                        from = &(*i);
                        to = &(*j);
                    }
                }
            }
        }

        if (from == NULL || to == NULL) { // не было ребер, соединяющих две доли старого MST
            cout<<"Error: MST is broken\n"<<endl;
            return false;
        } else {
            mst->add_edge(from->get_name(), to->get_name(), min);
        }
    }

    printGraph(mst);
    return true;
}

void executeCommand(BiGraph<int>& graph, BiGraph<int>* mst) {
    string command;
    while (true) {
        cin>>command;
        if (command == "exit") { return; }

        if (command == "add") {
            addEdge(graph, mst);
            continue;
        }

        if (command == "delete") {
            if (!deleteEdge(graph, mst)) { return; }
            continue;
        }

        cout<<"Unknown command: "<<command<<endl<<endl;
        continue;
    }
}

int main() {
    BiGraph<int> graph(false);
    readGraph(graph);
    BiGraph<int>* mst = graph.getMinSpanningTree();
    printGraph(mst);

    executeCommand(graph, mst);

    system("pause");
    return 0;
}
